package com.leetcode.algorithm.y22.m08.w3;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 451. 根据字符出现频率排序
 * 
 * https://leetcode.cn/problems/sort-characters-by-frequency/
 * 
 * @author jie.deng
 *
 */
class Question0451Solution01 {

	public String frequencySort(String s) {
		int[] cntArr = new int['z' - '0' + 1];
		int len = s.length();
		for (int i = 0; i < len; i++) {
			cntArr[s.charAt(i) - '0']++;
		}
		PriorityQueue<int[]> queue = new PriorityQueue<>((arr1, arr2) -> arr2[1] - arr1[1]);
		for (int i = 0; i < cntArr.length; i++) {
			if (cntArr[i] != 0) {
				queue.add(new int[] { i, cntArr[i] });
			}
		}

		StringBuilder builder = new StringBuilder();
		while (!queue.isEmpty()) {
			int[] arr = queue.poll();
			char ch = (char) (arr[0] + '0');
			int cnt = arr[1];
			char[] chs = new char[cnt];
			Arrays.fill(chs, ch);
			builder.append(chs);
		}
		return builder.toString();
	}

}